package com.ry.day1129;

import java.util.Stack;

public class LC3665 {


     static class ParentTreeNode {
          public int val;
          public ParentTreeNode parent, left, right;
      }


    static class Solution {
        /**
         * @param node: random node in binary search tree
         * @return: the inorder successor of current node
         */
        public ParentTreeNode inorderSuccessor(ParentTreeNode node) {
            //第一步：先找到根节点
            ParentTreeNode cur = node;
            ParentTreeNode root = node;
            while (cur!=null){
                root = cur;
                cur = cur.parent;
            }

            //中序遍历得到结果
            ParentTreeNode pre = null;
            Stack<ParentTreeNode> s = new Stack<>();
            while (!s.isEmpty() || root!=null){
                while (root!=null){
                    s.add(root);
                    root=root.left;
                }

                root = s.pop();

                if(pre ==node){
                    return root;
                }

                pre = root;
                root= root.right;
            }
            return null;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3665 · 二叉搜索树中的中序后继（二）
算法
中等
通过率
52%

题目
题解5
笔记
讨论1
排名
记录
描述
存在一颗二叉搜索树，且该二叉树节点持有其父亲节点 parent。

在本题中，你将获取到二叉搜索树的任意一个节点。你需要返回该节点在中序遍历顺序之后的那个节点，如果不存在后续节点则返回 null。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1

输入：

{2, 1, 3}
1
输出：

2
解释：

二叉搜索树如下所示：

  2
 / \
1   3
显然节点 1 的中序后驱节点为 2。

样例 2

输入：

{2, 1, 3}
3
输出：

null
标签
相关题目

448
二叉查找树的中序后继
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
8/77
已开启智能提示
发起考试
30 分 00 秒


 */
